package com.programmercarl.greed;

/**
 * https://leetcode.cn/problems/jump-game/description/
 * 跳跃游戏  参考
 *
 * @author yulongtian
 * @create 2025-02-06 16:50
 */
public class Test05 {
    public static void main(String[] args) {
        Test05 test05 = new Test05();
//        System.out.println(test05.canJump(new int[]{2, 0, 0}));
//        System.out.println(test05.canJump(new int[]{2, 5, 0, 0}));
//        System.out.println(test05.canJump(new int[]{2, 0, 1, 1, 2, 1, 0, 0, 0}));
        System.out.println(test05.canJump(new int[]{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}));
    }

    public boolean canJump(int[] nums) {
        int n = nums[0];
        for(int i = 0; i < nums.length; i++){
            if(nums[i] >= nums.length - i -1){
                return true;
            }
            //n代表最大步数，每走一步则减少一步，移动到下一个数进行比较
            //如果该步数比n更大或相等时，则用此步数替换掉n
            if(n > nums[i]){
                n--;
            }else{
                n = nums[i];
            }
            //当最大步数n为零则证明以及无法移动，返回false
            if(n == 0){
                return false;
            }
        }
        return true;
    }

}
